//Given a 2D matrix matrix, handle multiple queries of the following type: 
//
// 
// Calculate the sum of the elements of matrix inside the rectangle defined by 
//its upper left corner (row1, col1) and lower right corner (row2, col2). 
// 
//
// Implement the NumMatrix class: 
//
// 
// NumMatrix(int[][] matrix) Initializes the object with the integer matrix 
//matrix. 
// int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the 
//elements of matrix inside the rectangle defined by its upper left corner (row1, 
//col1) and lower right corner (row2, col2). 
// 
//
// 
// Example 1: 
//
// 
//Input
//["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
// [3, 0, 1, 4, 2],
// [5, 6, 3, 2, 1],
// [1, 2, 0, 1, 5],
// [4, 1, 0, 1, 7],
// [1, 0, 3, 0, 5],
// [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
//Output
//[null, 8, 11, 12]
//
//Explanation
//NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 
//0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
//numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
//numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
//
//numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)
// 
//
// 
// Constraints: 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 200 
// -10⁵ <= matrix[i][j] <= 10⁵ 
// 0 <= row1 <= row2 < m 
// 0 <= col1 <= col2 < n 
// At most 10⁴ calls will be made to sumRegion. 
// 
// Related Topics 设计 数组 矩阵 前缀和 👍 319 👎 0

package leetcode.editor.cn;

public class P304RangeSumQuery2dImmutable {
    public static void main(String[] args) {

        NumMatrix solution = new P304RangeSumQuery2dImmutable().new NumMatrix(
                new int[][]{
//                        {3, 0, 1, 4, 2},
//                        {5, 6, 3, 2, 1},
//                        {1, 2, 0, 1, 5},
//                        {4, 1, 0, 1, 7},
//                        {1, 0, 3, 0, 5}
                        {-4, -5}
                }
        );
//        System.out.println(solution.sumRegion(2, 1, 4, 3));
        System.out.println(solution.sumRegion(0,0,0,0));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class NumMatrix {
        int[][] arr;

//        public NumMatrix(int[][] nums) {
//            arr = new int[nums.length][nums[0].length];
//            for (int i = 0; i < nums.length; i++) {
//                int sum = 0;
//                for (int j = 0; j < nums[0].length; j++) {
//                    sum += nums[i][j];
//                    arr[i][j] = sum;
//                }
//            }
//        }
//
//        public int sumRegion(int row1, int col1, int row2, int col2) {
//            int sum = 0;
//            for (int i = row1; i <= row2; i++) {
//                if (col1 == 0) {
//                    sum += arr[i][col2];
//                } else {
//                    sum += arr[i][col2] - arr[i][col1 - 1];
//                }
//            }
//            return sum;
//        }

        public NumMatrix(int[][] nums) {
            arr = new int[nums.length][nums[0].length];
            for (int i = 0; i < nums.length; i++) {
                int sum = 0;
                for (int j = 0; j < nums[0].length; j++) {
                    sum += nums[i][j];
                    arr[i][j] = sum;
                    if (i > 0) {
                        arr[i][j] += arr[i - 1][j];
                    }
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = 0;
            int lowlow = arr[row1][col1];
            int highhigh = arr[row2][col2];
            int lowhigh = arr[row1][col2];
            int highlow = arr[row2][col1];

            if (row1 == 0 || col1 == 0) {
                lowlow = 0;
            } else if (row1 > 0 && col1 > 0) {
                lowlow = arr[row1 - 1][col1 - 1];
            }
            if (row1 == 0) {
                lowhigh = 0;
            } else if (row1 > 0) {
                lowhigh = arr[row1 - 1][col2];
            }
            if (col1 == 0) {
                highlow = 0;
            } else if (col1 > 0) {
                highlow = arr[row2][col1 - 1];
            }
            return highhigh - (highlow + lowhigh - lowlow);
        }
    }

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
//leetcode submit region end(Prohibit modification and deletion)

}